﻿namespace Algo.Search
{
    using System.Collections.Generic;

    internal abstract class DichotomySearchStrategy : IDichotomySearchStrategy
    {
        public bool Find<T>(IList<T> list, T item, IComparer<T> comparer, IAlgoExtensions extensions, out int? prev, out int? next)
        {
            var iterationsCount = 0;
            try
            {
                var count = list.Count;
                if (count == 0)
                {
                    prev = default(int?);
                    next = default(int?);
                    return false;
                }

                var compareResult = comparer.Compare(list[0], item);
                if (compareResult >= 0)
                {
                    iterationsCount++;
                    next = 0;
                    prev = compareResult == 0 ? next : default(int?);
                    return compareResult == 0;
                }

                compareResult = comparer.Compare(list[list.Count - 1], item);
                if (compareResult <= 0)
                {
                    iterationsCount++;
                    prev = list.Count - 1;
                    next = compareResult == 0 ? prev : default(int?);
                    return compareResult == 0;
                }

                var first = 0;
                var last = list.Count - 1;
                do
                {
                    var mid = GetMiddle(first, last);
                    if (comparer.Compare(list[mid], item) < 0)
                    {
                        first = mid + 1;
                    }
                    else
                    {
                        last = mid;
                    }

                    iterationsCount++;
                }
                while (first < last);

                compareResult = comparer.Compare(list[last], item);
                prev = last - (compareResult == 0 ? 0 : 1);
                next = last;
                return compareResult == 0;
            }
            finally
            {
                IMetricsExtension metricsBehaviour;
                if (extensions.TryGet(out metricsBehaviour))
                {
                    metricsBehaviour.RegisterIterations(iterationsCount);
                }
            }
        }

        protected abstract int GetMiddle(int first, int last);
    }
}
